4742. Количество делителей

Дано целое число n. Найдите количество его делителей, не считая 1 и само число n.

Вход. Одно натуральное число n (2 ≤ n ≤ 2³¹ – 1).

Выход. Выведите количество делителей числа n.

Пример входа	Пример выхода
18	4

РЕШЕНИЕ

математика – формула

Анализ алгоритма

Обозначим через d(n) количество делителей числа n. Очевидно, что d(1) = 1.

Пусть p – простое число. Тогда p имеет два делителя: 1 и p. Следовательно d(p) = 2.

Пусть n = p^k – степень простого числа. Тогда n имеет k + 1 делитель: 1, p, p², p³, …, p^k. Значит d(p^k) = k + 1.

Пусть n = p^kq^l. Рассмотрим два множества:

P ={1, p, p², p³, …, p^k } и Q ={1, q, q², q³, …, q^l }

Любой делитель d числа p^kq^l можно представить в виде x * y, где x ∈ P, y ∈ Q. Делитель x из P можно выбрать k + 1 способом, делитель y из Q можно выбрать l + 1 способом. Следовательно делитель d = x * y можно составить (k + 1) * (l + 1) способами.

Разложим число n на простые множители: n = . Количество делителей числа n равно

d(n) = (a₁ + 1) * (a₂ + 1) * … * (a_k + 1)

Пример

Число n = 18 имеет 6 делителей: 1, 2, 3, 6, 9, 18.

Разложим число n = 18 на простые множители:

18 = 2 * 3²

Следовательно

d(18) = (1 + 1) * (2 + 1) = 2 * 3 = 6

Вычитаем два делителя (1 и 18), получим ответ: 4 делителя.

Реализация алгоритма

Функция CountDivisors раскладывает число n на простые множители и вычисляет количество его делителей d(n).

int CountDivisors(int n)

{

int c, i, res = 1;

for(i = 2; i * i <= n; i++)

{

if (n % i == 0)

{

c = 0;

while(n % i == 0)

{

n /= i;

c++;

}

res *= (c + 1);

}

}

if (n > 1) res *= 2;

return res;

}

Основная часть программы. Читаем входное значение n.

scanf("%d",&n);

Вычисляем и выводим ответ. Из общего количества делителей d(n) вычитаем два делителя: 1 и само число n.

printf("%d\n",CountDivisors(n)-2);

Python реализация

import math

Функция CountDivisors раскладывает число n на простые множители и вычисляет количество его делителей d(n).

def CountDivisors(n):

res = 1;

for i in range(2, int(math.sqrt(n)) + 1):

if (n % i == 0):

c = 0

while (n % i == 0):

n //= i

c += 1

res *= (c + 1);

if (n > 1): res *= 2;

return res;

Основная часть программы. Читаем входное значение n.

n = int(input())

Вычисляем и выводим ответ. Из общего количества делителей d(n) вычитаем два делителя: 1 и само число n.

print(CountDivisors(n) - 2)